import data.structure.ListNode;

public class test34_11_11 {
    /*给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。



示例 1：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
*/
    public static void main(String[] args) {
        ListNode head = new ListNode(-1);
        head.next = new ListNode(5);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(0);
        ListNode result = sortList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        //先获取链表长度
        int length = 0;
        for (ListNode n = head; n != null; n = n.next) {
            length++;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //归并排序结合有序链表的合并
        for (int subLength = 1; subLength < length; subLength *= 2) {
            ListNode prev = dummy;
            ListNode curr = dummy.next;
            while (curr != null) {
                ListNode head1 = curr;//第一个链表头结点
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                //此时已经找到第二个链表头结点
                ListNode head2 = curr.next;
                //将第一个链表尾部断开
                curr.next = null;
                //将curr移动到后续要操作的链表上
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                //此时已经找到第一个和第二个链表的头结点，记住第二个链表尾部的下一个
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    //断开
                    curr.next = null;
                }
                //将第一个和第二个链表链接
                //将prev重新链接到主链表并移动到尾部
                prev.next = merged(head1, head2);
                while (prev.next != null)
                    prev = prev.next;
                //curr移动到下一个子链表
                curr = next;
            }
        }
        return dummy.next;
    }

    private static ListNode merged(ListNode head1, ListNode head2) {
        //head1和head2此时是有序的
        ListNode result = new ListNode(0);
        ListNode prev = result;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                prev.next = head1;
                prev = prev.next;
                head1 = head1.next;
            } else {
                prev.next = head2;
                prev = prev.next;
                head2 = head2.next;
            }
        }
        if (head1 != null) {
            prev.next = head1;
        } else prev.next = head2;
        return result.next;
    }
}
